package cc.wsyw126.java.nowcoder.interview;

import cc.wsyw126.java.lintCode.convert_binary_search_tree_to_doubly_linked_list.TreeNode;

import java.util.Stack;

/**
 * Created by Administrator on 2017/4/29.
 * 请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
 * 给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。
 * 保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。
 */
public class Successor {
    public int findSucc(TreeNode root, int p) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        boolean isFond = false;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            if (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                if (isFond) return pop.val;
                else if (pop.val == p){
                    isFond = true;
                }
                temp = pop.right;
            }
        }
        return -1;
    }
}
